#pragma once

#include "vector.h"
#include "box.h"
#include <list>
#include <set>
#include <hash_map>

namespace g3 {

template <typename T>
class hash_grid;

template <typename T>
class range_iterator
{
	typedef std::set<T> bucket;
	typedef typename std::set<T>::const_iterator bucket_iterator;
public:
	range_iterator();
	range_iterator(const hash_grid<T> & owner, const box &);
	range_iterator(const range_iterator &);
public:
	bool end() const;
	range_iterator & operator = (const range_iterator & rhs);
	bool operator == (const range_iterator & rhs) const;
	bool operator != (const range_iterator & rhs) const;
	range_iterator & operator ++ ();
	const T & operator * () const;
	//    const T * operator -> () const;
private:
	const hash_grid<T> *		_powner;
	boxi						_box;
	vectori						_pos;
	const bucket *				_pbucket;
	bucket_iterator				_it;
};

template <typename T>
class hash_grid
{
	typedef std::set<T> bucket;
	friend class range_iterator<T>;
public:
	typedef range_iterator<T> range_iterator;
public:
	hash_grid();
public:
	void reset(double cell_size);
	void insert(const box &, const T & value);
	range_iterator range_begin(const box &) const;
	range_iterator range_end() const;
private:
	const bucket * get_bucket(const vectori & pos) const;
	bucket * create_bucket(const vectori & pos);
private:
	typedef ::stdext::hash_map<vectori, bucket> hash_map;
	hash_map							_hash;
	/*
	typedef std::pair<vectori, bucket>	list_entry;
	typedef std::list<list_entry>			table_entry;
	std::vector<TableEntry>				d_Table;
	*/
	double								_cell;
};

} // g3


namespace stdext
{
	inline size_t hash_value(const g3::vectori & pos)
	{
//		return size_t(abs(11 * pos.x + 73 * pos.y + 113 * pos.z));
		return size_t(11 * pos.x + 73 * pos.y + 113 * pos.z);
	}
}

#include "hash_grid.inl"
